import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        arr = productExceptSelf(arr);
        System.out.println(Arrays.toString(arr));
    }
    //69.x的平方根
    public int mySqrt(int x) {
        if(x == 0 || x== 1) return x;
        if(x==2 || x == 3) return 1;
        long left = 2;
        long right = x;
        //查找右端点
        while(left < right) {
            long mid = left + (right-left+1)/2;
            if(mid * mid <=x) left = mid;
            else  right = mid-1;
        }
        return (int)left;
    }
    //238.除自身意外所有数的乘积
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] dp1 = new int[n];//dp[i]表示0下标到i下标所有元素之和
        int[] dp2 = new int[n];//dp[i]表示n-1下标到i+1下标所有元素之和
        dp1[0] = nums[0];dp2[n-1] = nums[n-1];
        for(int i=1;i<n;i++) {
            dp1[i] = nums[i]*dp1[i-1];
        }
        int k = 0;
        for(int i=n-2;i>=0;i--) {
            dp2[i] = nums[i]*dp2[i+1];
        }
        int[] answer = new int[n];
        answer[0] = dp2[1];answer[n-1]=dp1[n-2];
        for(int i=1;i<n-1;i++) {
            answer[i] = dp1[i-1]*dp2[i+1];
        }
        return answer;
    }

}
